package niuke.week02;

/**
 求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。
 */
public class MinDeepOfRoad {
     static class TreeNode {
        int val = 0;
        TreeNode left = null;
       TreeNode right = null;

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public TreeNode(int val) {
            this.val = val;
        }
    }


    public static void main(String[] args) {
        TreeNode node3 = new TreeNode(2, new TreeNode(1), new TreeNode(1));
        TreeNode node2 = new TreeNode(2, new TreeNode(1), null);
        TreeNode node1 = new TreeNode(3, node3, new TreeNode(4,new TreeNode(2),new TreeNode(1)));

        System.out.println(minDeep(node1));
        System.out.println(minDeep(node2));
        System.out.println(minDeep(node3));

    }

    public static int minDeep(TreeNode node){
        if(node.left==null && node.right==null)
            return 1;

        int minLeft = Integer.MAX_VALUE;
        int minRight = Integer.MAX_VALUE;

        if(node.left!=null)
            minLeft = minDeep(node.left);

        if(node.right!=null)
            minRight= minDeep(node.right);

        return Math.min(minLeft,minRight)+1;

    }


}